package 左神算法.排序;


/**
 * 快速排序
 *
 * @Author linhao
 * @Date created in 10:17 上午 2022/2/6
 */
public class QuickSort {

    public static int[] arr = {1, 3, 9, 9, 5, 4, 12, 4, 6, 7};

    public static void sort2(int[] arr,int leftBound,int rightBound){
        if(leftBound>=rightBound) return;
        int mid = partition(arr,leftBound,rightBound);
        sort2(arr,leftBound,mid-1);
        sort2(arr,mid+1,rightBound);
    }

    static int partition(int[] arr, int leftBound, int rightBound) {
        int pivot = arr[rightBound];
        int left = leftBound;
        int right = rightBound-1;
        while (left <= right) {
            while (left <= right && arr[left] <= pivot) left++;
            while (left <= right && arr[right] > pivot) right--;
            if (left < right) swap(arr, left, right);
        }
        swap(arr,left,rightBound);
        return left;
    }

    public static void sort(int[] arr, int left, int right) {
        int i = left;
        int k = right;
        int mid = (right + 1) / 2;
        int pivot = arr[mid];
        swap(arr, mid, k);
        k--;
        while (i < k) {
            if (arr[i] > pivot) {
                swap(arr, i, k);
                k--;
            } else {
                i++;
            }
        }
        if (i != right - 1) {
            swap(arr, k, right);
        }
    }

    public static void printArr(int[] arr) {
        for (Integer integer : arr) {
            System.out.print(integer + " ");
        }
        System.out.println("");
    }

    private static void swap(int[] arr, int k, int j) {
        int temp = arr[k];
        arr[k] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        QuickSort.sort2(arr, 0, arr.length-1);
        printArr(arr);
    }
}
